package com.dbh.alg.algorithm.hot150.链表;


import com.dbh.alg.algorithm.hot100.ListNode;

/**
 * 给你单链表的头指针 head 和两个整数 left 和 right ，
 * 其中 left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 */
public class Leetcode92_反转链表2 {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode s = new ListNode(-1);
        s.next = head;
        ListNode preLeft = s;
        // 移动到left-1位置
        for (int i = 0; i < left; i++) {
            preLeft = preLeft.next;
        }
        // 开始反转的节点是preLeft.next
        ListNode start = preLeft.next;
        ListNode cur = start;
        ListNode prev = null;
        ListNode next = null;

        // 反转left到right之间的节点
        for (int i = 0; i < right - left + 1; i++) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        // 此时prev是反转的头结点
        preLeft.next = prev;
        // cur是right的下一节点
        start.next = cur;

        return s.next;
    }
}
